package com.ly.algorithm.DataStructures.huffmantree;
import java.util.ArrayList;
import java.util.Comparator;
import	java.util.List;

/**
 * @Classname HuffManTree
 * @Description TODO
 * @Date 2020/5/2 17:11
 * @Author 冷心影翼
 */
public class HuffManTree {

    public Node root;

    public void createHuffManTree(List<Node> nodes) {
        while (nodes.size()>1) {
            nodes.sort(Comparator.comparingInt( n -> n.value));
            Node left = nodes.get(0);
            Node right = nodes.get(1);
            Node parent = new Node(left.value+right.value);
            parent.left = left;
            parent.right = right;
            nodes.remove(left);
            nodes.remove(right);
            nodes.add(parent);
        }
        root = nodes.get(0);
     }

     public void preOrder() {
        if(root!=null) {
            root.preOrder();
        }
     }
}

class Test {
    public static void main(String[] args) {
        int[] arr = {13,7,8,3,29,6,1};
        List<Node> nodes = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            nodes.add(new Node(arr[i]));
        }
        HuffManTree huffManTree = new HuffManTree();
        huffManTree.createHuffManTree(nodes);
        huffManTree.preOrder();
    }


}

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    public void preOrder() {
        System.out.println(this);
        if(left!=null) {
            left.preOrder();
        }
        if(right!=null) {
            right.preOrder();
        }
    }
//    @Override
//    public int compareTo(Node o) {
//        return this.value-o.value;
//    }

    @Override
    public String toString() {
        return "Node " +
                "value=" + value ;
    }
}
